Περιεχόμενα: Αλγόριθμοι και υπολογιστικά προβλήματα, Ανάλυση αλγορίθμων, Ασυμπτωτικοί συμβολισμοί, Αναδρομικές σχέσεις. Τεχνικές σχεδίασης: Διαίρει-και-Βασίλευε, Άπληστοι αλγόριθμοι, Δυναμικός προγραμματισμός. Αλγόριθμοι γραφημάτων: Αναζήτηση κατά πλάτος, Αναζήτηση σε βάθος, Τοπολογική ταξινόμηση, Ελάχιστα συνδετικά δέντρα, Συντομότερα μονοπάτια. Εισαγωγή στη θεωρία πολυπλοκότητας: Προβλήματα P, ΝP, και NP-πλήρη, Αναγωγές πολυωνυμικού χρόνου. Ειδικά θέματα: Προσεγγιστικοί αλγόριθμοι, Πιθανοτικοί αλγόριθμοι και Υπολογιστική γεωμετρία.

Στο τέλος του μαθήματος ο φοιτητής θα μπορεί να:

• περιγράφει αλγορίθμους για μία σειρά κλασσικών υπολογιστικών προβλημάτων και να παρουσιάζει την εκτέλεσή τους πάνω σε τυπικά στιγμιότυπα.
• εφαρμόζει τεχνικές σχεδίασης αλγορίθμων και να κατασκευάζει αποδοτικούς αλγορίθμους.
• διατυπώνει αλγορίθμους με σαφήνεια σε γραπτό λόγο και ψευδοκώδικα.
• αναλύει την πολυπλοκότητα ενός αλγορίθμου και να αποδεικνύει την ορθότητά του.
• διακρίνει βασικές έννοιες της θεωρίας ΝP-πληρότητας.

Αξιολόγηση: Εργασίες με βάρος 30%-40% και γραπτή εξέταση.

Μέθοδοι αξιολόγησης: Ερωτήσεις σύντομης απάντησης, Επίλυση προβλημάτων, Γραπτή εργασία.

https://eclass.uop.gr/courses/1768/

Βιβλιογραφία:

1. T. Cormen, C. Leiserson, R. Rivest, C. Stein, Εισαγωγή στους αλγορίθμους, 4η έκδοση, ΙΤΕ-Πανεπιστημιακές Εκδόσεις Κρήτης, 2025. ISBN: 9786182301302. Κωδικός στον Εύδοξο: 143555643.
2. J. Kleinberg, E. Tardos, Σχεδιασμός αλγορίθμων, 1η έκδοση, Κλειδάριθμος, 2009. Κωδικός στον Εύδοξο: 13898.
3. S. Dasgupta, C. Papadimitriou, U. Vazirani, Αλγόριθμοι, 1η έκδοση, Κλειδάριθμος, 2009. Κωδικός στον Εύδοξο: 13583.
4. M. Goodrich, R. Tamassia, Αλγόριθμοι Σχεδίαση και Εφαρμογές, 1η έκδοση, Γκιούρδας, 2016. Κωδικός στον Εύδοξο: 59359833.